package leetCode.sample;

import org.junit.Test;

public class MaxPathSumSolution {

    int max = Integer.MIN_VALUE;

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(-3);
        root.left = left;
        root.right = right;
        System.out.println(maxPathSum(root));
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traversalTree(root);
        return max;
    }

    private int traversalTree(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftMax = traversalTree(node.left);
        int rightMax = traversalTree(node.right);
        max = Math.max(node.val + leftMax + rightMax, max);
        int temp = Math.max(leftMax, rightMax) + node.val;
        return Math.max(temp, 0);
    }


}
